package com.example.arithmeticleetcode.learnArithmetic2.sort;

/**
 * @program: arithmetic-leetcode
 * @description:  最好，最坏，平均时间复杂度 O(nlogn)  空间复杂度 O(1) 属于不稳定排序
 * @author: FangZhen
 * @create: 2020-11-05 11:53
 **/
public class HeapSort<E extends Comparable<E>> extends Sort<E>{

    private int heapSize;

    @Override
    protected void sort() {
        //原地建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        while (heapSize > 1) {
            //交换堆顶元素与尾部元素
            swap(0, --heapSize);
            //对0位置进行siftdown(恢复堆的性质)
            siftDown(0);
        }
    }

    private void siftDown(int index) {
        E element = array[index];
        int half = heapSize >> 1;
        //第一个叶子节点的索引 == 非叶子节点的数量
        //必须保证index位置为非叶子节点
        while (index < half) {
            //index的节点有2种情况
            // 1 只有左子节点
            // 2 同时有左右子节点

            //默认为左子节点的索引
            int childIndex = (index << 1) + 1;
            E child = array[childIndex];

            //右子节点
            int rightIndex = childIndex + 1;

            //选出左右子节点最大的那个
            if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) {
                child = array[childIndex = rightIndex];
            }

            if (cmp(element, child) >= 0) break;

            //将子节点存放到index位置
            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }
}
